package Greed;

public class DiStringMatch {
    //增减字符串匹配
    public int[] diStringMatch(String s) {
        int n=s.length();
        char[] c=s.toCharArray();
        int[] a=new int[n+1];
        for (int i = 0; i <=n ; i++) {
            a[i]=i;
        }
        int left=0;
        int right=n;
        int[] ret=new int[n+1];
        for (int i = 0; i <n; i++) {
            if(c[i]=='I'){
                ret[i]=a[left++];
            }else {
                ret[i]=a[right--];
            }
        }
        ret[n]=a[left];
        return ret;
    }
}
